package day_2022_12_to_3.year2023;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author haomin
 * @date 2023/03/20 20:07
 **/
public class Day3_20_Num1012 {
    // 这道题，直接正面去解，不好解
    // 逆向找所有位上都不重复的数字个数，让n减去它就是结果
    class Solution {
        public int numDupDigitsAtMostN(int n) {
            List<Integer> list = new ArrayList<>();
            int res = n;
            // 先求出n一共包含几位数字，每位分别是多少
            while (n > 0) {
                list.add(n % 10);
                n /= 10;
            }
            int m = list.size(), cur = 0, sum = 0;
            // 假设n为47891
            // 求9999 999 99 9... 一共包含多少个不重复数字
            // 之所以这样求，是因为求47891共包含多少个各位都不重复的数字
            // 可以用把1~3 xxxx用3*9*8*7*6这样求得
            // 剩下的10000以内的就需要这样求得
            for (int i = 0; i < m - 1; i++) sum += 9 * jc(9, m - 2 - i);
            Set<Integer> set = new HashSet<>();
            // 按上面的类推
            // 先求1~3 xxxx共包含多少
            // 这样就能固定4 再确定 4 1~6 xxx共包含多少
            // 特殊情况如果 4400 求完第一位，到第二位重复了，后面的位就不需要计算了
            while (cur < m) {
                int v = list.get(m - 1 - cur);
                int tmp = 0;
                int start = 0, end = v - 1;
                if (cur == 0) start = 1;
                if (cur == m - 1) end = v;
                for (int i = start; i <= end; i++) if (set.isEmpty() || !set.contains(i)) tmp++;
                sum += tmp * jc(9 - cur, m - 1 - cur);
                if (set.contains(v)) break;
                set.add(v);
                cur++;
            }
            return res - sum;
        }

        private int jc(int cur, int n) {
            int sum = 1;
            while (n-- > 0) sum *= cur--;
            return sum;
        }
    }
}